from functools import cache


class Solution:
    def countSpecialNumbers(self, n: int) -> int:
        # 数位dp
        s=str(n)

        # 返回从i开始填数字，i前面填的数字的集合是mask，能构造出的特殊整数数目
        # is_limit 表示前面填的数字是否都是n对应位上的，如果为true，那么当前至多为int(s[i])，否者为9
        # in_num 表示前面是否填了数字（是否跳过），如果是true，那么当前位可以从0开始，如果为false，那么我们可以跳过，或者从1开始填数字
        @cache
        def f(i,mask,is_limit,is_num):
            if i==len(s):
                return int(is_num)
            res=0
            if not is_num: # 选择跳过，不填数字
                res=f(i+1,mask,False,False)
            up=int(s[i]) if is_limit else 9
            # 枚举要填的数字，枚举的范围就取决于is_limit 和 is_num
            for d in range(1-int(is_num),up+1):
                # mask，用于判断当前位是否填了数字
                if mask>>d&1==0:  # mask 里面没有d，表示没有填数字
                    res+=f(i+1,mask|(1<<d),is_limit and d==up,True)
            return res
        return f(0,0,True,False)
